import common.ListNode;

import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author tmh
 * @date 2024/10/16 20:33
 * @description
 */
public class T23合并K个升序链表 {
    //这道题可以使用堆，由于我们要让最后的结果升序，所以我们可以使用小根堆
    public ListNode mergeKLists(ListNode[] lists) {
        //堆再Java里面叫做优先级队列
        Queue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val-o2.val);
        //把lists里面的链表放入queue里面
        for (ListNode list : lists) {
            if (list!=null){
                queue.offer(list);
            }

        }
        ListNode dummyHead=new ListNode(0);
        ListNode tail = dummyHead;
        while (!queue.isEmpty()){
            ListNode temp = queue.poll();
            //让tail的next指向下一个节点temp
            tail.next=temp;
            //让tail指向temp
            tail=temp;
            if (temp.next!=null){
                queue.offer(temp.next);
            }
        }
        return dummyHead.next;
    }
}
